# 生成邻接矩阵 与 矩阵的运算
import numpy as np


# 复制数组
def my_copy_arr(init_graph):
    now_graph = np.ones(shape=(len(init_graph), len(init_graph)))
    for i in range(0, len(init_graph)):
        for j in range(0, len(init_graph)):
            now_graph[i][j] = init_graph[i][j]
    return now_graph


# 根据网络节点和通信半径生成邻接矩阵 值为0和1
def get_matrix_by_graph_and_radius(graph, radius):
    # 初始化邻接矩阵
    init_array = np.ones(shape=(len(graph), len(graph)))
    for i in range(0, len(graph)):
        for j in range(0, len(graph)):
            if i == j:
                continue
            x1 = graph[i][0]
            y1 = graph[i][1]
            x2 = graph[j][0]
            y2 = graph[j][1]
            if radius * radius >= (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2):
                init_array[i][j] = 1
            else:
                init_array[i][j] = 0
    return init_array


# 传入的数据为邻接矩阵 值为0和1(不为0) 矩阵相乘 再相加
def matrix_multiplication(init_graph, count):
    """
    :param init_graph: 原始邻接矩阵
    :param count: 相乘次数
    :return: 原始邻接矩阵的count次幂
    """
    res = my_copy_arr(init_graph)
    for i in range(1, count):
        res = np.matmul(res, init_graph)
    return res


# 检验是否连通 即邻接矩阵是否全不为0  网络全连通则返回True
def check_if_link(link_graph):
    for i in range(0, len(link_graph)):
        for j in range(0, len(link_graph)):
            if link_graph[i][j] == 0:
                return False
    return True


# 验证是否全连通
# a+a*a+a*a*a+a*a*a*a...
def check_n_is_link(init_graph, node_number):
    # 节点个数为1，直接返回真
    if node_number == 1:
        return True
    # 节点个数为2，直接验证并返回
    if node_number == 2:
        return init_array, check_if_link(init_graph)
    # 节点个数大于2 进行n-1次
    now_graph = my_copy_arr(init_graph)

    for count in range(2, node_number):
        now_graph += matrix_multiplication(init_graph, count)
        if not now_graph.__contains__(0):
            return now_graph, True

    return now_graph, check_if_link(now_graph)


if __name__ == '__main__':
    graph_node = [[1, 2], [3, 4]]
    init_array = get_matrix_by_graph_and_radius(graph_node, radius=4)
    isLink = check_n_is_link(init_array, 4)
    print(isLink)
